home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _dp_hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  31.2 KB  |  1,402 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _dp_hash.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. //------------------------------------------------------------------------------
  18. // Dynamic Perfect Hashing  [DKMMRT]
  19. //
  20. // Michael Wenzel           ( 1990/91 ) 
  21. //
  22. //------------------------------------------------------------------------------
  23.  
  24.  
  25. #include <LEDA/impl/dp_hash.h>
  26.  
  27.  
  28.  
  29. // ----------------------------------------------------------------
  30. // allgemeine Funktionen und Konstanten
  31. // ----------------------------------------------------------------
  32.  
  33.  
  34. // Universum [1..dp_exp_31-1]
  35. // 2-er Potenzen, Shift Operationen sparen
  36. #define dp_exp_31 2147483648
  37. #define dp_exp_30 1073741824
  38. #define dp_exp_29 536870912 
  39. #define dp_exp_28 268435456 
  40. #define dp_exp_27 134217728 
  41. #define dp_exp_26 67108864 
  42. #define dp_exp_25 33554432 
  43.  
  44.  
  45. // Konstante fuer Groesse beim Rehashing 
  46. #define _dp_h_c 1
  47.  
  48. // allgmeine Quadrat- und Multiplikationsfunktion fuer 2-er Potenz
  49. #define sqr(x) ((x)*(x))                  
  50. #define mal_pot2(x,y) ((x)<<(y))
  51.  
  52. // Berechnung von (k*x)%p
  53. // fuer p=2^31+11  ( kleinste Primzahl > 2^31 )
  54.  
  55.  
  56. #define DPMOD_BODY(k,x,dp_erg)\
  57. { unsigned dp_k1=k>>16;\
  58.   unsigned dp_k2=k&65535;\
  59.   unsigned dp_x1=(unsigned(x))>>16;\
  60.   unsigned dp_x2=(unsigned(x))&65535;\
  61.   unsigned dp_e1=dp_k1*dp_x1+((dp_k1*dp_x2+dp_k2*dp_x1)>>16);\
  62.   unsigned dp_e2=dp_k2*dp_x2;\
  63.   unsigned dp_e3=((dp_k1*dp_x2+dp_k2*dp_x1)&65535)<<16;\
  64.   unsigned dp_e5=dp_e2+dp_e3;\
  65.   if ((dp_e2&dp_exp_31)&&(dp_e3&dp_exp_31))\
  66.     dp_e1++;\
  67.   else if (((dp_e2&dp_exp_31)||(dp_e3&dp_exp_31))&&(!(dp_e5&dp_exp_31)))\
  68.      dp_e1++; \
  69.   long dp_f=(dp_e5&0x7fffffff)-22*(dp_e1&0x03ffffff);\
  70.   if (dp_e1&dp_exp_26)\
  71.     if(dp_f<1476394997)\
  72.       dp_f+=671088651;\
  73.     else dp_f-=1476395008;\
  74.   if (dp_e1&dp_exp_27)\
  75.     if(dp_f<805306346)\
  76.       dp_f+=1342177302;\
  77.     else dp_f-=805306357;\
  78.   if (dp_e1&dp_exp_28)\
  79.     if(dp_f<1610612703)\
  80.       dp_f+=536870945;\
  81.     else dp_f-=1610612714;\
  82.   if (dp_e1&dp_exp_29)\
  83.     if(dp_f<1073741758)\
  84.       dp_f+=1073741890;\
  85.     else dp_f-=1073741769;\
  86.   if (dp_e1&dp_exp_30)\
  87.     if(dp_f<2147483527)\
  88.       dp_f+=121;\
  89.     else dp_f-=2147483538;\
  90.   if (dp_e5&dp_exp_31)\
  91.     if (dp_f<0)\
  92.       dp_f+=2147483648;\
  93.     else dp_f-=11;\
  94.   if (dp_f<0)\
  95.     dp_erg=unsigned(dp_f+2147483659);\
  96.   else  dp_erg=unsigned(dp_f);\
  97. }
  98.  
  99. #ifdef __TURBOC__
  100.  
  101. /* Function "dpmod"  */
  102.  
  103. static void dpmod(unsigned k, GenPtr x, unsigned& dp_erg) DPMOD_BODY(k,x,dp_erg)
  104.  
  105. #else
  106.  
  107. /* Macro "dpmod" */
  108.  
  109. #define dpmod(k,x,dp_erg) DPMOD_BODY(k,x,dp_erg)
  110.  
  111. #endif
  112.  
  113.  
  114. // ----------------------------------------------------------------
  115. // member-functions of class headertable 
  116. // ----------------------------------------------------------------
  117.  
  118. //-----------------------------------------------------------------
  119. // insert
  120. // fuegt ein Paar (Schluessel,Information) in das Bucket ein
  121. // berechnet Informationen neu
  122. // returns true, falls Element eingefuegt     
  123.  
  124.  
  125. bool headertable::insert(GenPtr a,GenPtr b,stp& erg,int& bed,bool& rehash,
  126.              stp anf,stp ende)
  127. { 
  128.   unsigned dp_erg=0;
  129.   if (!wj)                             // leere Headertable
  130.   { 
  131.     wj=1;
  132.  
  133.     if (!tj)
  134.     { 
  135.       mj=1;
  136.       tj=new subtable(a,b);            // einfach einfuegen
  137.       erg=tj;
  138.     }
  139.     else                               // Tafel war angelegt
  140.     {
  141.       if (mj==1)                       // nur einelementig  
  142.       {
  143.     tj->set_s(a,b);
  144.     erg=tj;
  145.       }
  146.       else                             // groessere Tafel
  147.         if (mj<=4)                     // nur 2 oder 4-elementig  
  148.         {
  149.       tj[0].set_s(a,b);
  150.           erg=tj;
  151.         }
  152.     else
  153.         {
  154.           dpmod(kj,a,dp_erg);
  155.           dp_erg=dp_erg%mal_pot2(sqr(mj),1);
  156.           tj[dp_erg].set_s(a,b);
  157.           erg=tj+dp_erg;
  158.         }
  159.     }
  160.    
  161.     bed+=2; 
  162.     rehash=false;
  163.     return true;         
  164.   }                                    // leere Tafel jetzt mit Element
  165.  
  166.   if (wj==1)                           // Tafel mit einem Element
  167.   { 
  168.     if (mj==1)
  169.     {
  170.       if (a==tj->ke)                   // gleiches Element
  171.       { 
  172.         tj->inf=b;
  173.         erg=tj;
  174.         rehash=false;
  175.         return false; 
  176.       }
  177.       else
  178.       { 
  179.         wj=2;                          // Einfuegen
  180.         bed+=6;
  181.         if (bed>=0)                    // Platz genug?
  182.         { 
  183.           rehash=true;
  184.           return true; 
  185.         }
  186.  
  187.         mj=2;                          // Speicher anfordern
  188.                        // und Elemente verteilen
  189.         stp lj=tj;
  190.         tj=new subtable[2];
  191.         tj[0] = (*lj);
  192.         tj[1].set_s(a,b);
  193.         erg = tj+1;
  194.     
  195.         if ((lj>ende)||(lj<anf)) 
  196.           delete lj;
  197.       }
  198.  
  199.       rehash = false;
  200.       return true;
  201.     }
  202.  
  203.     if (mj<=4)
  204.     {
  205.       if (a==tj[0].ke)               // gleiches Element
  206.       { 
  207.         tj[0].inf=b;
  208.         erg=tj;
  209.         rehash=false;
  210.         return false; 
  211.       }
  212.       else
  213.       { 
  214.     wj = 2;
  215.         bed+=6;
  216.     tj[1].set_s(a,b);
  217.         erg = tj+1;
  218.     rehash=false;
  219.     return true;
  220.       }
  221.     }
  222.     else                               // groessere Tafel
  223.     {
  224.       dpmod(kj,a,dp_erg);
  225.       dp_erg=dp_erg%mal_pot2(sqr(mj),1);
  226.  
  227.       if (a==tj[dp_erg].ke)            // gleiches Element
  228.       { 
  229.     tj[dp_erg].inf = b;
  230.     erg=tj+dp_erg;
  231.     rehash=false;
  232.     return false;
  233.       }
  234.  
  235.       wj=2;
  236.       bed+=6;
  237.  
  238.       if ( tj[dp_erg].ke == EMPTY )    // Position leer
  239.       { 
  240.         tj[dp_erg].set_s(a,b);
  241.         erg=tj+dp_erg;
  242.     rehash=false;
  243.     return true;
  244.       }
  245.       else                             // lokales Rehash
  246.       { 
  247.     stp lj = new subtable(tj[dp_erg]);
  248.     tj[dp_erg].clear();
  249.     int subsize = mal_pot2(sqr(mj),1);
  250.         int injektiv=0;            
  251.                        // injektive Funktion suchen
  252.     
  253.         while (!injektiv)
  254.         { injektiv=1;
  255.           kj=urandom(1,maxprim-1);
  256.  
  257.           unsigned dp_erg=0;
  258.           dpmod(kj,lj->ke,dp_erg);
  259.           dp_erg=dp_erg%subsize;
  260.           tj[dp_erg]=(*lj);
  261.  
  262.           dpmod(kj,a,dp_erg);
  263.           dp_erg=dp_erg%subsize;
  264.           if ( tj[dp_erg].ke == EMPTY )
  265.           {
  266.         tj[dp_erg].set_s(a,b);
  267.         erg=tj+dp_erg;
  268.           }
  269.           else
  270.           {
  271.             tj[dp_erg].clear(); 
  272.             injektiv=0;
  273.           }
  274.         }                              // Elemente injektiv verteilt 
  275.  
  276.         delete lj;
  277.         rehash=false;
  278.         return true;           
  279.       }
  280.     }
  281.   }                                    // Tafel enthaelt jetzt 2 Elemente
  282.  
  283.   if (wj<4)                            // Tafel mit 2 oder 3 Elementen
  284.   { 
  285.     for (int i1=0; i1<wj ; i1++)
  286.       if (a==tj[i1].ke)                // gleiches Element
  287.       { 
  288.         tj[i1].inf=b;
  289.         erg=tj+i1;
  290.         rehash=false;
  291.         return false; 
  292.       }
  293.  
  294.                        // neues Element
  295.     if (wj==2)
  296.       bed+=10;
  297.     else
  298.       bed+=14;
  299.  
  300.     if (mj==2)
  301.     {
  302.       if (bed>=0)                      // Platz genug?
  303.       { 
  304.         rehash=true;
  305.         return true; 
  306.       }
  307.  
  308.       mj=4;                            // Speicher anfordern
  309.       stp lj=tj;
  310.       tj=new subtable[4];
  311.  
  312.       for (int i1=0; i1<wj ; i1++)
  313.         tj[i1] = lj[i1];
  314.       tj[i1].set_s(a,b);
  315.       erg = tj+wj;
  316.     
  317.       if ((lj>ende)||(lj<anf)) 
  318.         delete lj;
  319.  
  320.       wj++;       
  321.       rehash = false;
  322.       return true;
  323.     }
  324.  
  325.     if (mj==4)
  326.     {
  327.       tj[wj].set_s(a,b);
  328.       erg = tj+wj;
  329.       wj++;       
  330.       rehash=false;
  331.       return true;
  332.     }
  333.     else                               // groessere Tafel
  334.     {
  335.       dpmod(kj,a,dp_erg);
  336.       dp_erg=dp_erg%mal_pot2(sqr(mj),1);
  337.       if ( tj[dp_erg].ke == EMPTY )    // Position leer
  338.       { 
  339.         tj[dp_erg].set_s(a,b);
  340.         erg=tj+dp_erg;
  341.         wj++;       
  342.     rehash=false;
  343.     return true;
  344.       }
  345.       else                             // lokales Rehash
  346.       {
  347.     stp lj = new subtable[++wj];
  348.         int i1=0;
  349.                                             // Elemente in Liste kopieren
  350.         for (int i2=0; i1<wj-1 ; i2++ )
  351.         { 
  352.       if ( tj[i2].ke != EMPTY  )
  353.           { 
  354.         lj[i1++]=tj[i2];  
  355.             tj[i2].clear(); 
  356.       }
  357.         }
  358.         lj[i1].set_s(a,b);
  359.  
  360.         int subsize = mal_pot2(sqr(mj),1);
  361.         int injektiv=0;                     // injektive Funktion suchen
  362.     
  363.         while (!injektiv)
  364.         { injektiv=1;
  365.           kj=urandom(1,maxprim-1);
  366.  
  367.           for (i1=0; (i1<wj) && injektiv ; i1++)
  368.           { 
  369.             dpmod(kj,lj[i1].ke,dp_erg);
  370.             dp_erg=dp_erg%subsize;
  371.  
  372.             if ( tj[dp_erg].ke == EMPTY )
  373.               tj[dp_erg]=lj[i1];
  374.             else
  375.             { 
  376.           injektiv=0;
  377.               for (int g=0;g<i1;g++)     // belegte Positionen loeschen
  378.               { 
  379.             GenPtr help=lj[g].ke;
  380.                 dpmod(kj,help,dp_erg);
  381.                 dp_erg=dp_erg%subsize;  
  382.                 tj[dp_erg].ke = EMPTY ; 
  383.                  }
  384.             }
  385.           }                            // Elemente injektiv verteilt  
  386.         }       
  387.  
  388.         delete lj;
  389.         rehash=false;
  390.         return true;           
  391.       }                                // lokales Rehash beendet
  392.     }
  393.   }                                    // Tafel enthaelt jetzt 2 oder 3 Elemente
  394.  
  395.   if (wj==4)                           // Tafel mit 4 Elementen
  396.   { 
  397.     for (int i1=0; i1<4; i1++)
  398.       if (a==tj[i1].ke)                // gleiches Element
  399.       { 
  400.         tj[i1].inf=b;
  401.         erg=tj+i1;
  402.         rehash=false;
  403.         return false; 
  404.       }
  405.   
  406.                        // neues Element einfuegen
  407.     bed+=18;
  408.  
  409.     if (bed>=0)                        // Platz genug?
  410.     { 
  411.       rehash=true;
  412.       return true; 
  413.     }
  414.  
  415.     mj=8;                               // Speicher anfordern
  416.                     // und Elemente verteilen
  417.     stp lj=tj;
  418.     tj=new subtable[128];
  419.     int injektiv=0;       
  420.                     // injektive Funktion suchen
  421.     
  422.     while (!injektiv)
  423.     {
  424.       injektiv=1;
  425.       kj=urandom(1,maxprim-1);
  426.  
  427.       for (int i1=0; (i1<4) && injektiv ; i1++)
  428.       { 
  429.         dpmod(kj,lj[i1].ke,dp_erg);
  430.         dp_erg=dp_erg%128;
  431.  
  432.         if ( tj[dp_erg].ke == EMPTY )
  433.           tj[dp_erg]=lj[i1];
  434.         else
  435.         { 
  436.       injektiv=0;
  437.           for (int g=0;g<i1;g++)     // belegte Positionen loeschen
  438.           { 
  439.         GenPtr help=lj[g].ke;
  440.             dpmod(kj,help,dp_erg);
  441.             dp_erg=dp_erg%128;  
  442.             tj[dp_erg].ke = EMPTY ; 
  443.              }
  444.         }
  445.       }
  446.       if (injektiv)                  // letztes Element hashen
  447.       {
  448.         dpmod(kj,a,dp_erg);
  449.         dp_erg=dp_erg%128;
  450.         if ( tj[dp_erg].ke == EMPTY )
  451.         { 
  452.           tj[dp_erg].set_s(a,b);
  453.           erg=tj+dp_erg;
  454.         }
  455.         else
  456.         { 
  457.           injektiv=0;
  458.           for (int g=0;g<i1;g++)     // belegte Positionen loeschen
  459.           { 
  460.             GenPtr help=lj[g].ke;
  461.             dpmod(kj,help,dp_erg);
  462.             dp_erg=dp_erg%128;  
  463.             tj[dp_erg].clear() ; 
  464.           }
  465.         }                            // letztes Element 
  466.       }             
  467.     }                                // Elemente injektiv verteilt 
  468.  
  469.     if ((lj>ende)||(lj<anf)) 
  470.       delete lj;
  471.  
  472.     wj=5;                          
  473.     rehash=false;
  474.     return true;           
  475.   }                             // Tafel enthaelt jetzt 5 Elemente
  476.  
  477.                                 // Tafel mit >= 5 Elementen
  478.                 // injektives Hashing auf Bucket
  479.  
  480.   int subsize=mal_pot2(sqr(mj),1);
  481.   dpmod(kj,a,dp_erg);
  482.   dp_erg=dp_erg%subsize;
  483.  
  484.   if ( tj[dp_erg].ke == a)         // gleiches Element
  485.   { 
  486.     tj[dp_erg].set_s(a,b);
  487.     erg=tj+dp_erg;
  488.     rehash=false;
  489.     return false;      
  490.   }
  491.  
  492.   int oldscard=wj;
  493.   int subcard=(++wj);
  494.   bed+=mal_pot2(subcard,2)-2;
  495.  
  496.   if ( tj[dp_erg].ke == EMPTY  )    // Position leer -> einfuegen
  497.   { 
  498.     tj[dp_erg].set_s(a,b);
  499.     erg=tj+dp_erg;
  500.     rehash = false;
  501.     return true; 
  502.   }
  503.   else                         // Tafelelement besetzt             
  504.    
  505.     if (subcard<=mj)           // aber noch Platz in Tafel
  506.     {  
  507.       stp lj = new subtable[subcard];
  508.       int i1=0;
  509.                                // Elemente in Liste kopieren
  510.       for (int i2=0; i1<oldscard  ; i2++ )
  511.       {
  512.     if ( tj[i2].ke != EMPTY  )
  513.         {
  514.           lj[i1++]=tj[i2];  
  515.           tj[i2].clear(); 
  516.         }
  517.       }
  518.       lj[i1].set_s(a,b);
  519.                                  // lokales Rehash , alle Elemente in Liste lj
  520.  
  521.       int injektiv=0;
  522.       while (!injektiv)          // injektive Funktion suchen
  523.       { 
  524.     injektiv=1;
  525.         kj=urandom(1,maxprim-1);
  526.  
  527.         for (i1=0; (i1<subcard) && injektiv ; i1++)
  528.         { 
  529.           dpmod(kj,lj[i1].ke,dp_erg);
  530.           dp_erg=dp_erg%subsize;
  531.           if ( tj[dp_erg].ke == EMPTY )
  532.           {
  533.             tj[dp_erg]=lj[i1]; 
  534.         erg=tj+dp_erg;
  535.           }
  536.           else
  537.           {
  538.         injektiv=0;                // Injektivitaet verletzt
  539.             for (int g=0;g<i1;g++)     // belegte Positionen loeschen
  540.             {
  541.           GenPtr help=lj[g].ke;
  542.           dpmod(kj,help,dp_erg);
  543.               dp_erg=dp_erg%subsize;  
  544.               tj[dp_erg].ke = EMPTY ; 
  545.                }
  546.           }
  547.         }                       // Elemente getestet
  548.  
  549.       }                         // naechster Versuch oder fertig
  550.  
  551.       delete lj;
  552.       rehash = false;
  553.       return true; 
  554.     }                             // subcard<=mj
  555.  
  556.     else                          // |Wj|>Mj , d.h. Groesse der
  557.                                 // Subtable verdoppeln
  558.     { 
  559.       if (bed>=0)                 // Kontrolle des Platzverbrauchs
  560.       {
  561.         rehash = true;
  562.         return true;    
  563.       }
  564.       else                        // Platz in Ordnung             
  565.                                   // Untertafel verdoppeln
  566.       { 
  567.         int oldssize= mal_pot2(sqr(mj),1);
  568.         int i1=0;
  569.                                   // Elemente in Liste retten
  570.         stp lj = new subtable[subcard]; 
  571.         for (int i2=0; i1<oldscard ; i2++)
  572.           if ( tj[i2].ke != EMPTY  )
  573.             lj[i1++]=tj[i2];
  574.         lj[i1].set_s(a,b);
  575.  
  576.         for ( ; mj<wj ; mj<<=1 ) ;    // Subtable vergroessern
  577.         subsize = mal_pot2(sqr(mj),1); 
  578.  
  579.         if ((tj>ende)||(tj<anf))      // Speicherverwaltung
  580.           delete tj;
  581.  
  582.         tj=new subtable[subsize]; 
  583.         int injektiv=0;
  584.                                       // injektive Funktion suchen
  585.         while (!injektiv)       
  586.         {
  587.           injektiv=1;
  588.           kj=urandom(1,maxprim-1);
  589.           for (i1=0; (i1<subcard) && injektiv ; i1++)
  590.           {
  591.             dpmod(kj,lj[i1].ke,dp_erg);
  592.             dp_erg=dp_erg%subsize;
  593.             if ( tj[dp_erg].ke == EMPTY )
  594.             { 
  595.               tj[dp_erg]=lj[i1]; 
  596.               erg=tj+dp_erg;
  597.             }
  598.  
  599.              else                       // Injektivitaet verletzt
  600.              {
  601.            injektiv=0;
  602.                for (int g=0;g<i1;g++)   // Subtables saeubern
  603.                {
  604.          GenPtr help=lj[g].ke;
  605.          dpmod(kj,help,dp_erg);
  606.                  dp_erg=dp_erg%subsize;
  607.          tj[dp_erg].ke = EMPTY ; 
  608.            }
  609.  
  610.          }
  611.           }                             // alle Elemente getestet
  612.  
  613.         }                               // naechster Versuch oder fertig
  614.  
  615.         delete lj;
  616.       rehash = false;
  617.     return true;
  618.       }
  619.     }
  620.   }                       // insert
  621.    
  622. //-----------------------------------------------------------------
  623. // dinsert
  624. // fuegt ein Paar (Schluessel,Information) in das Bucket ein
  625. // benutzt Informationen aus Konstruktor oder Rehash_all
  626. // gibt true zurueck, falls erfolgreich
  627.  
  628.  
  629. int headertable::dinsert(GenPtr a,GenPtr b,
  630.               stp ende,stp& wo,stp& erg)
  631.  
  632. {
  633.   if (mj==1)                    // nur ein Element in Tafel 
  634.   {                // und Tafel anlegen  
  635.     tj=wo;
  636.     wo++; 
  637.     tj->set_s(a,b);    
  638.     erg=tj;
  639.     return true;  
  640.   }                             // leere Tafel jetzt mit Element
  641.  
  642.   if (mj==2)                    // zwei Elemente in Tafel 
  643.   {
  644.     if (!tj)               // und Tafel anlegen
  645.     { 
  646.       wj=1;
  647.       tj=wo;
  648.       wo+=2; 
  649.       tj[0].set_s(a,b);    
  650.       erg=tj;
  651.       return true;  
  652.     }                           // leere Tafel jetzt mit Element
  653.     else
  654.     { 
  655.       if (a==tj[0].ke)
  656.       {
  657.     tj[0].inf = b;
  658.     erg = tj;
  659.     return false;
  660.       }
  661.       wj=2;
  662.       tj[1].set_s(a,b);
  663.       erg=tj+1;
  664.       return true;
  665.     }
  666.   }
  667.  
  668.   if (mj<=4)                    // max 4 Elemente in Tafel 
  669.   {
  670.     if (!tj)               // und Tafel anlegen
  671.     { 
  672.       wj=1;
  673.       tj=wo;
  674.       wo+=4; 
  675.       tj[0].set_s(a,b);    
  676.       erg=tj;
  677.       return true;  
  678.     }                           // leere Tafel jetzt mit Element
  679.     else
  680.     { 
  681.       for (int i1=0; i1<wj; i1++)
  682.         if (a==tj[i1].ke)
  683.         {
  684.       tj[i1].inf = b;
  685.       erg = tj+i1;
  686.       return false;
  687.         }
  688.  
  689.       tj[wj].set_s(a,b);
  690.       erg=tj+wj;
  691.       wj++;
  692.       return true;
  693.     }
  694.   }
  695.  
  696.  
  697.  
  698.   if (!tj)                      // Tafel muss angelegt werden
  699.                 // Tafel mit meheren Elementen
  700.                 // erstes Element kommt hinein
  701.   { 
  702.     int q=mal_pot2(sqr(mj),1);  // Platz anfordern aus Pool
  703.     tj=wo;
  704.     wo+=q; 
  705.     if (wo>ende+1)
  706.       error_handler(1,"memory allocation error");
  707.  
  708.     kj=urandom(1,maxprim-1);     // erstes Element einfuegen
  709.     unsigned dp_erg=0;
  710.     dpmod(kj,a,dp_erg);
  711.     dp_erg=dp_erg%q;
  712.     tj[dp_erg].set_s(a,b);
  713.     erg=tj+dp_erg;
  714.     wj = 1;                     // jetzt aktuelles wj
  715.     return true;       
  716.   }                             // leere Tafel jetzt mit 1.Element
  717.  
  718.                                 // Tafel ist schon angelegt und enthaelt Element
  719.                                 // Tafel bekommt mindestens 5 Elemente
  720.   unsigned dp_erg=0;
  721.   int subsize=mal_pot2(sqr(mj),1);
  722.   dpmod(kj,a,dp_erg);
  723.   dp_erg=dp_erg%subsize;
  724.  
  725.   if ( tj[dp_erg].ke == a)           // gleicher Schluessel
  726.   { 
  727.     tj[dp_erg].set_s(a,b);
  728.     erg=tj+dp_erg;
  729.     return false;      
  730.   }
  731.  
  732.   if ( tj[dp_erg].ke == EMPTY  )     // Position leer
  733.   { tj[dp_erg].set_s(a,b);   
  734.     erg=tj+dp_erg;
  735.   }
  736.  
  737.   else                          // Position besetzt -> lokales Rehash 
  738.   {  
  739.                 // Elemente sammeln
  740.      stp lj = new subtable[wj+1];
  741.      int i1=0;
  742.      int i2=0;
  743.      for (i2=0; i1<wj ; i2++)   // Elemente in Liste kopieren
  744.      { if ( tj[i2].ke != EMPTY  )
  745.        { lj[i1++]=tj[i2];  
  746.          tj[i2].clear() ; 
  747.        }
  748.      }
  749.  
  750.      lj[i1++].set_s(a,b);         // i1 = wj+1
  751.  
  752.                                   // lokales Rehash , alle Elemente in Liste lj
  753.      int injektiv=0;
  754.                                   // injektive Funktion suchen
  755.      while (!injektiv)         
  756.      {
  757.        injektiv=1;
  758.        kj=urandom(1,maxprim-1);
  759.  
  760.        for (i2=0; (i2<i1) && injektiv ; i2++)
  761.        { 
  762.          dpmod(kj,lj[i2].ke,dp_erg);
  763.      dp_erg=dp_erg%subsize;
  764.          if ( tj[dp_erg].ke == EMPTY )
  765.      {
  766.        tj[dp_erg]=lj[i2]; 
  767.        erg=tj+dp_erg;
  768.          }
  769.          else                      // Injektivitaet verletzt
  770.          {
  771.        injektiv=0;
  772.            for (int g=0;g<i2;g++)  // Subtables saeubern
  773.            {
  774.          GenPtr help=lj[g].ke;
  775.              unsigned dp_erg=0;
  776.          dpmod(kj,help,dp_erg);
  777.              dp_erg=dp_erg%subsize;
  778.              tj[dp_erg].ke = EMPTY ;
  779.        }
  780.          }
  781.        }                           // alle Elemente getestet 
  782.  
  783.      }                             // neuer Versuch oder fertig
  784.  
  785.      delete lj;
  786.   }
  787.  
  788.   wj++;                           // aktuelle Anzahl updaten
  789.   return true;
  790.  
  791. }
  792.  
  793.  
  794. // ----------------------------------------------------------------
  795. // lookup
  796. // sucht nach Eintrag mit Schluessel a
  797. // gibt Pointer auf Eintrag zurueck, falls gefunden
  798. // 0 sonst
  799.  
  800. stp headertable::lookup(GenPtr a)
  801.  
  802. { 
  803.    if (!wj)  return 0;              // Headertable leer
  804.  
  805.    if (mj==1)                       // Headertable einelementig
  806.    { 
  807.      if (a==tj->ke) 
  808.        return tj;
  809.      else
  810.        return 0;
  811.    }
  812.  
  813.    if (mj<=4)                       // Tafel mit max 4 Elementen
  814.    { 
  815.      for (int i1=0; i1<wj; i1++)
  816.        if (a==tj[i1].ke) 
  817.          return tj+i1;
  818.      return 0;
  819.    }
  820.                                     // Headertable mit mehr als 4 Subtables
  821.    unsigned dp_erg=0;
  822.    dpmod(kj,a,dp_erg);
  823.    dp_erg=dp_erg%(mal_pot2(sqr(mj),1));   // Position
  824.  
  825.    if (tj[dp_erg].ke==a)
  826.      return tj+dp_erg;
  827.    else
  828.      return 0; 
  829.  } 
  830.  
  831. // ----------------------------------------------------------------
  832. // del
  833. // loescht Element in Tafel
  834. // gibt true zurueck, wenn erfolgreich
  835.  
  836. bool headertable::del(GenPtr a,stp anf,stp ende)
  837.  
  838. {
  839.   if (!wj) return false;             // leere Headertable
  840.  
  841.   if (mj==1)                         // Headertable einelementig
  842.   { 
  843.     if (a==tj->ke) 
  844.     {
  845.       wj=0;                          // Schluessel gefunden
  846.       tj->clear() ;
  847.       if ((tj<anf)||(tj>ende))
  848.       {
  849.     delete tj;
  850.     tj = 0;
  851.     mj = 0;
  852.       } 
  853.       return true;    
  854.     }
  855.     else
  856.       return false;
  857.   }
  858.      
  859.   if (mj<=4)           
  860.   { 
  861.     if (wj>1)                        // Headertable mit mind 2 Elementen
  862.     {
  863.       for (int i1=0; i1<wj; i1++)
  864.       { 
  865.     if (tj[i1].ke==a)            // Element gefunden
  866.         { 
  867.           wj--;
  868.           tj[i1]=tj[wj];             // Loch fuellen
  869.           tj[wj].clear();
  870.           return true;
  871.         }
  872.       }
  873.       return false;
  874.     }
  875.     else                               // ein Element in Bucket
  876.     {
  877.       if (tj[0].ke==a) 
  878.       {
  879.     wj=0;                          // Schluessel gefunden
  880.         tj[0].clear() ;
  881.         if ((tj<anf)||(tj>ende))
  882.         {
  883.       delete tj;
  884.       tj = 0;
  885.       mj = 0;
  886.         } 
  887.         return true;    
  888.       }
  889.       else
  890.         return false;
  891.     }
  892.   }
  893.      
  894.                       // Headertable mit mehreren Subtables
  895.   unsigned dp_erg=0;
  896.   dpmod(kj,a,dp_erg);
  897.   dp_erg=dp_erg%(mal_pot2(sqr(mj),1));   // Position
  898.  
  899.   if (tj[dp_erg].ke==a)
  900.   {
  901.     wj--;                             // Schluessel gefunden
  902.     tj[dp_erg].clear() ;
  903.  
  904.     if (wj==0)                        // Bucket nun leer
  905.       if ((tj<anf)||(tj>ende))
  906.       {
  907.     delete tj;
  908.     tj = 0;
  909.     mj = 0;
  910.       } 
  911.     return true;    
  912.   } 
  913.   else return false;
  914. }
  915.  
  916. // ---------------------------------------------------------
  917. // give_elements()
  918. // haengt Elemente der Tafel an Liste an
  919. // gibt Anzahl der Elemente zurueck
  920.  
  921.  
  922. int headertable::give_elements(stp& wo,stp anf,stp ende)
  923.  
  924. { 
  925.   int j=0;
  926.  
  927.   if (!wj) { 
  928.          if ( tj && ((tj<anf)||(tj>ende))) 
  929.              {
  930.            if (mj>1)
  931.                  delete tj;
  932.            else 
  933.                  delete tj;
  934.  
  935.            tj = 0;
  936.            mj = 0;
  937.              }
  938.          return 0;
  939.        }
  940.  
  941.   if (mj==1)                    // Headertable einelementig
  942.   { 
  943.     (*wo)=(*tj);                // Element kopieren
  944.     wo++;
  945.     if ((tj<anf)||(tj>ende))     // gebe Speicher frei
  946.     {
  947.       delete tj;
  948.       tj = 0;
  949.       mj = 0;
  950.     }
  951.     return 1; 
  952.   }
  953.  
  954.   if (mj<=4)                     // Headertable maximal vierelementig
  955.   { 
  956.     j=0;   
  957.     while ( (tj[j].ke != EMPTY) && (j<mj) )
  958.     { 
  959.       (*wo)=tj[j];
  960.       wo++;
  961.       j++;
  962.     }
  963.  
  964.     if ((tj<anf)||(tj>ende))     // gebe Speicher frei
  965.     { 
  966.       delete tj;
  967.       tj = 0;
  968.       mj = 0;
  969.     }
  970.     return j; 
  971.   }
  972.  
  973.                  // Headertable mit meheren Elementen
  974.   bool weiter=true;
  975.   int subsize=mal_pot2(sqr(mj),1);
  976.   j=0;
  977.  
  978.   for (int k=0;(k<subsize)&&weiter;k++)  // suche Elemente
  979.     if ( tj[k].ke != EMPTY  )
  980.     {                                    // haenge Element an Liste
  981.       (*wo)=tj[k];
  982.       wo++; j++;
  983.       if (j>=wj) weiter=false; 
  984.     }
  985.   if ((tj<anf)||(tj>ende))               // gebe Speicher frei
  986.   { 
  987.     delete tj;
  988.     tj = 0;
  989.     mj = 0;
  990.   }
  991.   return j;
  992. }
  993.  
  994. // ----------------------------------------------------------------
  995. // member-functions of class dp_hash
  996. // ----------------------------------------------------------------
  997.  
  998. // -------------------------------------------------------
  999. // rehash_all
  1000. //
  1001. // stellt Headertables neu auf, um Platzverbrauch korrekt
  1002. // zu halten
  1003. // fuegt Element dann neu ein
  1004.  
  1005. stp dp_hash::rehash_all( GenPtr x=EMPTY , GenPtr y=0 )
  1006.  
  1007. { 
  1008.   int i,i1,j,nsave,platz;
  1009.   unsigned dp_erg=0;
  1010.  
  1011.   stp erg=0;
  1012.   stp l=new subtable[n];         // Sammle Elemente in Liste l
  1013.  
  1014.   i=0;
  1015.   stp pos = l;
  1016.   nsave = ( x == EMPTY ? n : n-1 );
  1017.  
  1018.   while ( (i<sM) && (nsave>0) )  // Sammle Element aus allen Headertables
  1019.   { 
  1020.     if (htablep[i])
  1021.     {
  1022.       nsave -= htablep[i]->give_elements(pos,anf,ende) ;
  1023.       delete htablep[i];
  1024.     }
  1025.     i++;   
  1026.   }
  1027.  
  1028.   if ( x != EMPTY )               // fuege neues Element hinzu
  1029.     l[n-1].set_s(x,y);
  1030.  
  1031.   free ((char*)htablep);          // Speicher freigeben
  1032.   if (anf) 
  1033.     delete anf; 
  1034.                         // neue Parameter setzen
  1035.  
  1036.   M=int((1+_dp_h_c)*n);
  1037.   sM = int(((4.0/3.0)*wursechs)*(1+_dp_h_c)*n);
  1038.  
  1039.                                   // Speicher allokieren
  1040.   htablep=(htp*) calloc(sM,sizeof(htp));  // schneller als new+init
  1041.   int* buckets=new int[n];
  1042.  
  1043.   if (!htablep)
  1044.     error_handler(1,"memory overflow");
  1045.  
  1046.   platz=n;
  1047.   i1=0;
  1048.   while (!i1)                    // Top-Funktion suchen
  1049.   { 
  1050.     bed=0;
  1051.     k=urandom(1,maxprim-1);
  1052.     for (i=0;i<n;i++)           // Hashe alle Elemente
  1053.     {
  1054.       GenPtr help=l[i].ke;
  1055.       dpmod(k,help,dp_erg);
  1056.       dp_erg=dp_erg%sM;
  1057.       buckets[i] = dp_erg;      // Merke Headertable
  1058.  
  1059.       if (!htablep[dp_erg]) 
  1060.         htablep[dp_erg] = new headertable;
  1061.  
  1062.                                 // Aendere Headertables
  1063.       int f=++(htablep[dp_erg]->wj);
  1064.       int* groesse=&(htablep[dp_erg]->mj);
  1065.  
  1066.       if (f<=2)
  1067.      (*groesse)++;
  1068.       else
  1069.         if (*groesse<f)
  1070.         { 
  1071.       (*groesse)<<=1;      
  1072.   
  1073.       if (*groesse==4)       // vergroessere Feld
  1074.         platz++;
  1075.           else
  1076.         if (*groesse==8)     // Uebergang von Feld auf Tafel
  1077.           platz+=123;
  1078.             else
  1079.           platz+=3*sqr(*groesse)/2; 
  1080.         }
  1081.     else                     // Tafel nicht vergroessert
  1082.       platz--;
  1083.  
  1084.       bed+=mal_pot2(f,2)-2; 
  1085.     }                            // alle Elemente gehasht
  1086.  
  1087.                                  // bed-=(((8.0*sqr(M))/sM)+2*M);
  1088.     float _bed=(wursechs+2)*M;   // Vereinfachung durch Einsetzen von sM
  1089.     bed-=int(_bed);
  1090.     i1=(bed<0);                  // kontrolliere Platz
  1091.  
  1092.     if (!i1)                     // nicht erfolgreich, saeubere Headertables
  1093.     {
  1094.       platz=n;
  1095.       for (j=0; j<sM; j++)
  1096.         if (htablep[j]) 
  1097.     { 
  1098.       delete htablep[j];
  1099.       htablep[j] = 0 ;   
  1100.     }
  1101.     }
  1102.  
  1103.   }                              // Top-Funktion gefunden
  1104.  
  1105.  
  1106.   anf=new subtable[platz];        // allokiere Speicher fuer alle Subtables
  1107.   wo=anf;
  1108.   ende=anf+platz-1;
  1109.  
  1110.   for (i=0; i<n; i++)             // fuege Elemente wieder ein
  1111.   { 
  1112.     int bucket=buckets[i];  
  1113.     htablep[bucket]->dinsert(l[i].ke,l[i].inf,ende,wo,erg);
  1114.   }
  1115.  
  1116.   delete buckets;
  1117.   delete l;
  1118.   return erg;
  1119. }
  1120.  
  1121. // --------------------------------------------------------
  1122. // insert
  1123. //
  1124. // fuegt Element in die entsprechende Headertable ein
  1125.  
  1126. stp dp_hash::insert(GenPtr x,GenPtr y)
  1127.  
  1128. { 
  1129.   if ( (unsigned)x>maxuni )  
  1130.     error_handler(2,string("dp_hash: key %d out of range",x));
  1131.  
  1132.   copy_key(x);
  1133.   copy_inf(y);
  1134.  
  1135.   unsigned dp_erg=0;
  1136.   dpmod(k,x,dp_erg);
  1137.   dp_erg=dp_erg%sM;                   // Toptafel
  1138.  
  1139.   bool rehash = false;
  1140.   stp  erg    = 0;
  1141.  
  1142.   if ( !htablep[dp_erg] ) 
  1143.     htablep[dp_erg] = new headertable;
  1144.  
  1145.   if ( htablep[dp_erg]->insert(x,y,erg,bed,rehash,anf,ende) )  n++;
  1146.  
  1147.   if ( rehash )  erg=rehash_all(x,y);
  1148.  
  1149.   return erg;
  1150. }
  1151.  
  1152. // --------------------------------------------------------
  1153. // del
  1154. //
  1155. // loescht Element aus entsprechender Headertable
  1156.  
  1157. void dp_hash::del(GenPtr x)
  1158.  
  1159. { 
  1160.  
  1161.   if ( (unsigned)x>maxuni )  
  1162.     error_handler(2,string("key %d out of range",x));
  1163.  
  1164. // s.n. :
  1165.  
  1166. stp p = lookup(x);
  1167. if (p==0) return;
  1168. clear_key(p->ke);
  1169. clear_inf(p->inf);
  1170.  
  1171.  
  1172.   unsigned dp_erg=0;
  1173.   dpmod(k,x,dp_erg);
  1174.   dp_erg=dp_erg%sM;                   // Toptafel
  1175.  
  1176.   if ( !htablep[dp_erg] ) return;     // Headertable nicht vorhanden
  1177.                         // in Toptafel loeschen
  1178.  
  1179.   if ( htablep[dp_erg]->del(x,anf,ende) ) n--;     
  1180.  
  1181.   if ( !htablep[dp_erg]->wj )
  1182.   { 
  1183.     delete htablep[dp_erg];
  1184.     htablep[dp_erg] = 0;
  1185.   }
  1186.  
  1187.   if ((n*(1+3*_dp_h_c)<M) && (n>3))
  1188.     rehash_all(); 
  1189.  
  1190. } 
  1191.  
  1192. // -------------------------------------------------------
  1193. // lookup,change_inf
  1194. //
  1195. // suchen in Headertable nach Element mit Schluessel
  1196. // change_inf setzt Information des Elementes auf y
  1197.  
  1198.  
  1199. stp dp_hash::lookup(GenPtr x) const 
  1200.  
  1201. { 
  1202.   if ( (unsigned)x>maxuni )  
  1203.     error_handler(2,string("key %d out of range",x));
  1204.  
  1205.   unsigned dp_erg=0;
  1206.   dpmod(k,x,dp_erg);
  1207.   dp_erg=dp_erg%sM;                   // Toptafel
  1208.  
  1209.   if (!htablep[dp_erg]) 
  1210.     return 0;
  1211.  
  1212.   stp y=htablep[dp_erg]->lookup(x);
  1213.   return y ;
  1214.  
  1215. }
  1216.  
  1217. stp dp_hash::change_inf(GenPtr x,GenPtr y)      
  1218. { 
  1219.   if ( (unsigned)x>maxuni )  
  1220.     error_handler(2,string("key %d out of range",x));
  1221.  
  1222.   unsigned dp_erg=0;
  1223.   dpmod(k,x,dp_erg);
  1224.   dp_erg=dp_erg%sM;                   // Toptafel
  1225.  
  1226.  
  1227.   if (!htablep[dp_erg])
  1228.     return 0;
  1229.  
  1230.   stp t = htablep[dp_erg]->lookup(x) ;
  1231.   if (t)
  1232.     t->inf = y ;
  1233.   return t;
  1234.  
  1235. }
  1236.  
  1237. // -------------------------------------------------------
  1238. // clear
  1239. //
  1240. // loescht alle Elemente und
  1241. // setzt Hashing auf Leerzustand
  1242.  
  1243. void dp_hash::clear()
  1244.  
  1245. { 
  1246.   stp l = new subtable[n];
  1247.   stp pos=l;
  1248.  
  1249.   for (int i=0;i<sM;i++)           // Headertables loeschen
  1250.     if (htablep[i])
  1251.     { 
  1252.       htablep[i]->give_elements(pos,anf,ende);
  1253.       delete htablep[i];                         
  1254.     }
  1255.  
  1256.   free ((char*)htablep) ;          // Speicher freigeben
  1257.  
  1258.   if (anf) 
  1259.     delete anf;
  1260.  
  1261.   delete l;
  1262.  
  1263.   n = 0;                           // Leerinitialisierung
  1264.   M=4;
  1265.   sM=13;
  1266.   k=urandom(1,maxprim-1);
  1267.   bed=-17;
  1268.   htablep=(htp*) calloc(sM,sizeof(htp));
  1269.   anf = wo = ende = 0;
  1270.  
  1271. }
  1272.  
  1273. // ------------------------------------------------------------
  1274. // Konstruktoren und Destruktor
  1275.  
  1276. dp_hash::dp_hash()
  1277.  
  1278. { 
  1279.   n=0;
  1280.   M=4;
  1281.   sM=13;
  1282.   k=urandom(1,maxprim-1);
  1283.   bed=-17;
  1284.   htablep=(htp*) calloc(sM,sizeof(htp));
  1285.   anf = wo = ende = 0;
  1286.  
  1287. }
  1288.  
  1289. dp_hash::dp_hash(int an,GenPtr* keys,GenPtr* inhalte)   
  1290.                                           // wie rehash_all
  1291.                                           // die Elemente stehen aber schon in Listen
  1292. { 
  1293.   int i,i1,j,nsave,platz;
  1294.   unsigned dp_erg=0;
  1295.   stp erg=0;
  1296.  
  1297.   n=an;
  1298.   M=int((1+_dp_h_c)*n);
  1299.   sM = int(((4.0/3.0)*wursechs)*(1+_dp_h_c)*n);
  1300.  
  1301.   htablep=(htp*) calloc(sM,sizeof(htp));
  1302.   int* buckets = new int[n];
  1303.  
  1304.   if (!htablep)
  1305.     error_handler(1,"memory overflow");
  1306.  
  1307.   platz=n;
  1308.   i1=0;
  1309.  
  1310.   while (!i1)
  1311.   {
  1312.     bed=0;
  1313.     k=urandom(1,maxprim-1);
  1314.  
  1315.     for (i=0;i<n;i++)
  1316.     {
  1317.       GenPtr help=keys[i];
  1318.       if ( (unsigned)help>maxuni )  
  1319.          error_handler(2,string("key %d out of range",help));
  1320.  
  1321.       dpmod(k,help,dp_erg);
  1322.       dp_erg=dp_erg%sM;
  1323.       buckets[i] = dp_erg;
  1324.  
  1325.       if (!htablep[dp_erg]) 
  1326.     htablep[dp_erg] = new headertable;
  1327.  
  1328.       int f=++(htablep[dp_erg]->wj);
  1329.       int* groesse=&(htablep[dp_erg]->mj);
  1330.  
  1331.       if (f<=2)
  1332.      (*groesse)++;
  1333.       else
  1334.         if (*groesse<f)
  1335.         { 
  1336.       (*groesse)<<=1;      
  1337.   
  1338.       if (*groesse==4)       // vergroessere Feld
  1339.         platz++;
  1340.           else
  1341.         if (*groesse==8)     // Uebergang von Feld auf Tafel
  1342.           platz+=123;
  1343.             else
  1344.           platz+=3*sqr(*groesse)/2; 
  1345.         }
  1346.     else                     // Tafel nicht vergroessert
  1347.       platz--;
  1348.  
  1349.       bed+=mal_pot2(f,2)-2; 
  1350.     }
  1351.     
  1352.                                  // bed-=(((8.0*sqr(M))/sM)+2*M);
  1353.     float _bed=(wursechs+2)*M;   // Vereinfachung durch Einsetzen von sM
  1354.     bed-=int(_bed);
  1355.     i1=(bed<0);
  1356.  
  1357.     if (!i1)
  1358.     { 
  1359.       platz=n;
  1360.       for (j=0; j<sM; j++)
  1361.     if (htablep[j]) 
  1362.     { 
  1363.       delete htablep[j];
  1364.       htablep[j] = 0;   
  1365.     }
  1366.     }
  1367.   }
  1368.  
  1369.   nsave=an;
  1370.   anf=new subtable[platz];
  1371.  
  1372.   wo=anf;
  1373.   ende=wo+platz-1;
  1374.   n=0;
  1375.  
  1376.   for (i=0; i<nsave; i++)
  1377.   {
  1378.     int bucket = buckets[i];
  1379.     n += (htablep[bucket]->dinsert(keys[i],inhalte[i],ende,wo,erg));
  1380.   } 
  1381.  
  1382.   delete buckets;
  1383.  
  1384.   if ((n*(1+3*_dp_h_c)<M) && (n>3))
  1385.     rehash_all();   
  1386.  
  1387. }
  1388.  
  1389. dp_hash::~dp_hash()
  1390. { 
  1391.   clear();                            // loesche alles
  1392.  
  1393.   free ((char*)htablep);              // gebe Speicher frei
  1394.   if (anf) delete anf;
  1395.  
  1396.   n=M=sM=0;
  1397.   k=0;
  1398.   anf=wo=ende=0;
  1399.   htablep=0;
  1400.  
  1401. }
  1402.